package StackAndQueue;

import java.util.LinkedList;

public class p239滑动窗口最大值 {
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            // 确定返回数组大小
            int[] res = new int[nums.length + 1 - k];
            MyQueue myQueue = new MyQueue();
            int num = 0;
            // 加入滑动窗口中的元素
            for (int j = 0; j < k; j++) {
                myQueue.add(nums[j]);
            }
            res[num++] = myQueue.getMax();
            for (int i = k; i < nums.length; i++) {
                myQueue.poll(nums[i - k]);
                myQueue.add(nums[i]);
                res[num++] = myQueue.getMax();
            }
            return res;
        }
    }

    class MyQueue{
        LinkedList<Integer> queue = new LinkedList<>();

        // 对列的对顶元素始终为最大值
        public int getMax(){
            return queue.peek();
        }

        // 添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
        public void add(int e){
            while (!queue.isEmpty() && e > queue.getLast()){
                queue.removeLast();
            }
            queue.add(e);
        }

        // 如果弹出元素等于滑动窗口中最大的元素则弹出
        public void poll(int e){
            if (!queue.isEmpty() && e == getMax()){
                queue.poll();
            }
        }
    }
}
